from typing import List, Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if len(inorder) == 0:
            return None
        root = TreeNode(postorder[-1])
        i_index = inorder.index(postorder[-1])
        li, ri = inorder[:i_index], inorder[i_index + 1:]
        ll, rl = len(li), len(ri)
        if ll != 0:
            root.left = self.buildTree(li, postorder[:ll])
        if rl != 0:
            root.right = self.buildTree(ri, postorder[ll:ll+rl])
        return root
        if len(inorder) == 0:
            return None
        root = TreeNode(postorder[-1])
        i_index = inorder.index(postorder[-1])
        li, ri = inorder[:i_index], inorder[i_index + 1:]
        print('LR', li, ri)
        ll, rl = len(li), len(ri)
        if ll != 0:
            root.left = self.buildTree(li, postorder[:ll])
        if rl != 0:
            root.right = self.buildTree(ri, postorder[ll:ll+rl])
        return root

if __name__ == '__main__':
    s = Solution()
    s.buildTree(inorder = [9,3,15,20,7], postorder = [9,15,7,20,3])
